package linkedList;

import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: 链表习题
 * User: 王圆豪
 * Date: 2024-08-13
 * Time: 0:42
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(5);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(7);
        ListNode l = reverseKGroup(l1, 2);
        while (l != null) {
            System.out.println(l.val + " ");
            l = l.next;
        }
    }

    //K个一组翻转链表

// 一开始自己写的
    public static ListNode reverseKGroup(ListNode head, int k) {
        int o = 0;
        ListNode h = head;
        ListNode ll = null;
        ListNode pp = null;
        while (true) {
            if (ifMove(head, k)){
                ListNode kk = head;
                ListNode cur2 = head;
                head = move(head, k);
                ListNode cur1 = head;
                ListNode cur3 = cur2.next;
                while (cur2 != head) {
                    cur2.next = cur1;
                    cur1 = cur2;
                    cur2 = cur3;
                    if (cur3 != null) {
                        cur3 = cur3.next;
                    }
                }
                if (ll == null) {
                    ll = cur1;
                }else {
                    ll = cur1;
                    pp.next = ll;
                }
                pp = kk;
                if (o == 0) {
                    h = cur1;
                    o++;
                }
            }else {
                if (pp != null) {
                    pp.next = head;
                }
                break;
            }
        }
        return h;
    }

//看完答案后写的
public static ListNode reverseKGroup1(ListNode head, int k) {

        return null;
}
    public static ListNode move(ListNode head, int k) {
        while (k != 0 && head != null) {
            head = head.next;
            k--;
        }
        return head;
    }
    public static boolean ifMove(ListNode head, int k) {
        while (k != 1 && head != null) {
            head = head.next;
            k--;
        }
        return head != null;
    }

    //两两交换链表中的节点
    public static ListNode swapPairs(ListNode head) {
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while (head != null && head.next != null) {
            ListNode pp = head.next.next;
            cur.next = head.next;
            cur = cur.next;
            cur.next = head;
            cur = cur.next;
            head = pp;
        }
        cur.next = head;
        return newHead.next;
    }
    //合并K个升序链表
    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode newHead = new ListNode();
        ListNode cur = newHead;

        while (true) {
            ListNode min = null;
            int pos = -1;
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null && (min == null || lists[i].val < min.val)) {
                    min = lists[i];
                    pos = i;
                }
            }
            if (pos == -1) {
                break;
            }
            cur.next = min;
            lists[pos] = lists[pos].next;
            cur = cur.next;
        }
        return newHead.next;
    }

    public static boolean isEmpty(ListNode[] lists) {
        for (ListNode list : lists) {
            if (list != null) {
                return false;
            }
        }
        return true;
    }
    //删除链表的倒数第N个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (n != 0 && fast != null) {
            fast = fast.next;
            n--;
        }
        if (fast == null) {
            head = head.next;
        }else {
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
        }
        return head;
    }
    //两数相加
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        int p = 0;
        //找出长链表
        int count1 = 0;
        int count2 = 0;
        while (cur1 != null) {
            count1++;
            cur1 = cur1.next;
        }
        while (cur2 !=null) {
            count2++;
            cur2 = cur2.next;
        }
        if (count1 < count2) {
            cur1 = l2;
            cur2 = l1;
        }else {
            cur1 = l1;
            cur2 = l2;
        }
        ListNode cur = cur1;
        //遍历相加
        ListNode l3 = null;
        while(cur1 != null) {
            if (cur1.next == null) {
                l3 = cur1;
            }
            if (cur2 == null){
                int k = p + cur1.val;
                p = k / 10;
                cur1.val = k % 10;
                cur1 = cur1.next;
            }else {
                int k = cur1.val + cur2.val;
                k += p;
                cur1.val = k % 10;
                p = k / 10;
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }
        if (p != 0){
            l3.next = new ListNode(p);
        }
        return cur;
    }

    public static void main1(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(4);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(7);
        ListNode[] lists = new ListNode[]{l1, l2};
        ListNode listNode = mergeKLists(lists);
        while (listNode != null) {
            System.out.println(listNode.val + " ");
            listNode = listNode.next;
        }
    }
}
